{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 作业4 空间查询处理和优化"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "姓名：郑昱笙"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "学号：3180102760"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**作业目的：**理解(空间)查询处理与优化流程，掌握关系代数优化和基于代价的查询规划，掌握空间填充曲线在常用空间查询下的代价，掌握PostgreSQL的查询规划和GiST索引创建与使用，理解索引在基于代价的查询规划中的作用。\n",
    "\n",
    "**注意事项：**\n",
    "* SQL语句的错误输出为乱码时，修改SET client_encoding = 'GBK';或SET client_encoding = 'UTF-8';，重新连接数据库\n",
    "* Jupyter Notebook对SQL语句的错误提示较弱，可以先在pgAdmin 4上执行，查看详细的错误信息\n",
    "* 作业4总分50分，作业考察的题目后面标了具体分数，可以相互讨论思路，作业抄袭或雷同都要扣分\n",
    "* **作业4\\_学号\\_姓名.ipynb**替换其中的学号和姓名，包含执行结果，压缩为__作业4\\_学号\\_姓名.rar/zip__，**不要包含数据文件**，提交到学在浙大，作业4截止日期**2020.4.26**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 空间计算（2分）\n",
    "\n",
    "2016年Communications of The ACM上发表了一篇[Spatial Computing](http://www.cad.zju.edu.cn/home/ybtao/sdb/resources/CACM2016.pdf)论文，中文翻译[空间计算](http://www.cad.zju.edu.cn/home/ybtao/sdb/resources/CCCF2016.pdf)，其主要观点如下：\n",
    "* Starting with the public availability of GPS, spatial computing has enriched our lives through location-based services (such as Google Maps, Uber, geotagging, and geotargeted, including Amber, alerts).\n",
    "* It has also advanced computer science through ideas like spatial databases (such as R-tree and OGIS simple features library), spatial statistics (such as point process theory and Kriging), and spatial data mining (such as robust hotspot detection).\n",
    "* Future potentially transformative opportunities include ubiquitous indoor location-based services, the location-aware Internet of Physical Things, continuous global monitoring, visualization, forecast, alerts, and warnings to address societal challenges like climate change and how to provide adequate food, energy, and water.\n",
    "\n",
    "阅读该论文，根据文中内容回答以下问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.1 空间数据库的哪些方面在已有的空间计算中发挥了重要作用？（1分）"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "空间数据库引入的空间数据类型、操作、空间数据结构以及算法用来表达及有效执行多级并发空间查询，在已有的空间计算中发挥了重要作用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.2 从近期和长远来看，空间计算将如何促进空间数据库和空间统计的发展？（1分）"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "从近期来看，如机器学习方法这样的新空间模型在对一系列问题进行时空预测方面有着极其宝贵的价值；空间计算技术将互联网从网络空间向位置感知的物联网扩展，能够实现静止构造物与移动物体间的互联，帮助协调各类目标的运动，掌握城市内外的流动模式；空间计算可以扩展到室内、水下和地下空间，带来更丰富的数据和应用场景；\n",
    "从长远来看，志愿者用户所提供的地理信息将会越来越多地成为地理数据的来源，要从传统的数据融合向数据协同这一更广泛的范式转变；随着智能手机和基于 Web 的虚拟地球的普及，我们需要新的基础设施来支持空间计算；每天使用基于位置服务的民众自己成为了制图者，，需要新的方法来了解我们的空间能力以及不同群体思考空间的方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 代价估计与索引（14分）\n",
    "\n",
    "健身俱乐部设计了如下数据库，用来记录俱乐部会员：<br/>\n",
    "&ensp;&ensp;&ensp; Gym (<u>gid</u>, name, city)<br/>\n",
    "&ensp;&ensp;&ensp; Member (<u>mid</u>, name, is_student, birthdate, city)<br/>\n",
    "&ensp;&ensp;&ensp; Visits (<u>timestamp</u>, <u>mid</u> References Member, gid References Gym)<br/>\n",
    "\n",
    "Member和Visits在数据库中的统计信息如下：<br/>\n",
    "T(Member) = 500, B(Member) = 100, V(Member, city) = 10, V(Member, is_student) = 2<br/>\n",
    "T(Visits) = 5000, B(Visits) = 400, V(Visits, mid) = 500<br/>\n",
    "其中T表示关系的记录数目，B表示关系的磁盘页或Block数目，V表示属性不同取值的个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1 对于查询<br/>\n",
    "&ensp;&ensp;&ensp; Select name <br/>\n",
    "&ensp;&ensp;&ensp; From Member <br/>\n",
    "&ensp;&ensp;&ensp; Where city = '杭州' and is_student = True;<br/>\n",
    "基于下列条件估计磁盘I/O cost，即Block的读取块数。对于$\\sigma_{a=?}(R)$查询，返回的记录数目为T(R) * 1 / V(R,a) (5分)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1.1 没有索引"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1.2 Member的city属性上有非聚集索引"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 500/10 = 50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1.3 Member的city属性上有聚集索引"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100/10 = 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1.4 Member的is_student属性上有非聚集索引"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1.5 Member的(city, is_student)属性上有非聚集索引"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 500/10/2 = 25"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.2 对于查询<br/>\n",
    "&ensp;&ensp;&ensp; Select name, count(\\*) <br/>\n",
    "&ensp;&ensp;&ensp; From Member M, Visits V <br/>\n",
    "&ensp;&ensp;&ensp; Where M.mid = V.mid and city = '杭州' and is_student = True <br/>\n",
    "&ensp;&ensp;&ensp; Group By name;<br/>\n",
    "考虑查询中的Join部分，可以使用nested loop, merge join, hash join等算法。假设内存足够大，没有临时表存储到磁盘，基于以下等价的关系代数查询树，估计磁盘I/O cost。对于$R\\Join S$查询，nested loop的I/O cost为B(R) + B(R) \\* B(S)或B(S) + B(R) \\* B(S)。(5分)\n",
    "<img src = \"querytree.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2.1 基于左边查询树(先Join后Select)，没有索引，使用nested loop的最小I/O cost"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100+100*400 = 40100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2.2 基于左边查询树(先Join后Select)，Visits的mid属性上有非聚集索引，使用nested loop with index的最小I/O cost"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100+100*10 = 1100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2.3 基于左边查询树(先Join后Select)，Visits的mid属性上有聚集索引，使用nested loop with index的最小I/O cost"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 100+100*1 = 200"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2.4 基于右边查询树(先Select后Join)，Member的(city,is_student)属性上有非聚集索引，使用nested loop的的I/O cost"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 25+25*400 = 10025"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2.5 基于右边查询树(先Select后Join)，Member的(city,is_student)属性上有非聚集索引，Visits的mid属性上有非聚集索引，使用nested loop的的I/O cost"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Cost = 25+25*10 = 275"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.3 你构建了索引选择工具来度量某个索引对常用查询的性能提升(越高越好)。索引1(city, is_student)带来的性能提升是10，索引2(city, is_student, birthday)带来的性能提升是12，索引3(city, birthday)带来的性能提升是7。假设你只能保留2个索引，你会选择哪两个索引，理由是什么？(2分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "选择索引2和索引3；\n",
    "对于可以使用索引1的查询也可以使用索引2来提升性能，但可以使用索引3的查询并不能使用索引2来加速，因此去除索引1可以得到最大的查询性能提升；（12 + 7 = 19）\n",
    "\n",
    "也可以选择索引1和索引3，这样在能提升大多数查询的速度的前提下也可以使插入新数据的性能更好（7 + 10 = 17）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "2.4 健身俱乐部发现会员签到非常慢，邀请你来优化他们的数据库。在分析数据库后，你发现属性上创建了很多索引，包括Visits上的mid聚集索引。为什么mid聚集索引会使用户签到变慢，即插入一个新的Visit变慢？你需要什么信息来决定保留哪些索引和删除哪些索引？(2分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "聚集索引是指数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同，mid聚集索引要求在签到插入新的元组时需要查找到能保持mid聚集索引顺序的位置进行插入而不能随便插入，在预留空间满的情况下进行插入可能还会要求在该新插入元组之后的元组顺序后移，因此速度较慢。\n",
    "需要的信息：\n",
    "可以保留经常出现在常用查询的where、join等子句中的属性上的索引；对于不常见的时间效率要求不高的操作可以不建立索引；索引可能减慢插入删除操作的效率，因此对于插入删除效率要求比较快的可以不建立索引；对于数据量较大且重复值较少的表建立索引的效率会比较高，数据量少或者数据有大量重复值的表可以不建立索引；还需要了解部署数据库的机器的内存磁盘访问性能等等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.5 (附加题) 你和你的朋友同时到达杭州紫金港健身俱乐部，一起签到时，发生了如下错误：\n",
    "\n",
    "    Error: Duplicate entry '1586224200' for key 'pk_visits'\n",
    "    \n",
    "你觉得DBA在创建关系时做错了什么，导致了这个错误？如何进行修正这个错误？(2分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "timestamp：1586224200 转换为北京时间为 2020-04-07 09:50:00\n",
    "因此DBA很可能是将 pk_visits 的 timestamp 设置为了唯一的主键，导致了在同一时间签到会发生主键冲突；\n",
    "将主键设置为pk_visits（timestamp）和 mid（References Member mid）可解决问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 空间填充曲线 (10分)\n",
    "\n",
    "15个点存储在空间数据库中，如下图标识的A-O点，假设每个数据页最多存储两个数据点，Point Query和Nearest Neighbor Query为红色查询点，Range Query为黑色查询框。\n",
    "<img src = \"curve.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1 假设这些点使用heap file存储，即乱序存储，以下查询需要访问多少数据页？(3分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Point Query: 8\n",
    "Range Query: 8\n",
    "Nearest Neighbor Query: 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.2 构建4x4的Hilbert Curve，数据点按照Hilbert value的顺序存储，使用()表示一个数据页，给出数据点在数据库中的存储顺序。(2分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "(A, B)(E, D)(I, L)(M, J)(N, O)(K, H)(G, F)(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.3 基于Hilbert Curve存储的数据点，以下查询需要访问最少多少数据页？假设内存足够大，不需要重复读取数据页，未使用B+Tree对Hilbert Value构建索引。(5分)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Point Query: 需要访问3个数据页\n",
    "具体步骤：\n",
    "Ceil((0+7)/2) = 4, 该页数据点为N、O，Hilbert value值比查询值大；\n",
    "Ceil((0+3)/2) = 2，该页数据点为I、L，Hilbert value值比查询值小；\n",
    "Ceil((2+3)/2) = 3，该页数据点为M、J，\n",
    "M Hilbert value值比查询值小, J Hilbert value值比查询值大，未找到查询点，miss；\n",
    "\n",
    "Range Query: 需要访问6个数据页\n",
    "具体步骤：\n",
    "查询区域有交集的区块Hilbert value为2、7、8、11、12、13\n",
    "Ceil((0+7)/2) = 4, 该页数据点为N、O，Hilbert value为9、10\n",
    "Ceil((4+7)/2) = 6，该页数据点为G, F，Hilbert value为13满足范围查询条件，向上搜索页5，该页数据点为K, H，Hilbert value为11、12，满足Hilbert value但不在查询范围内；\n",
    "Ceil((0+3)/2) = 2，该页数据点为I, L，Hilbert value为4、5；\n",
    "Ceil((0+2)/2) = 1，该页数据点为E, D，Hilbert value为2、3，满足Hilbert value但不命中；\n",
    "Ceil((2+3)/2) = 3，该页数据点为M, J，Hilbert value为6、8，命中；\n",
    "\n",
    "Nearest Neighbor Query: 需要访问5个数据页\n",
    "具体步骤：采用两阶段算法：\n",
    "先进行Point Query: 需要访问3个数据页；\n",
    "此时内存中的数据块为2、3、4；\n",
    "假设内存足够大，不需要重复读取数据页，对访问3个数据页中间最近的点I，以查询点和I的距离作为查询半径进行范围查询，和查询区域有交集的区块Hilbert value为2、3、4、7，其中4、7已经被访问过在内存中；\n",
    "Ceil((0+2)/2) = 1，该页数据点为E, D，Hilbert value为2、3，没有更近的点；\n",
    "由于此时每个区块可以有多个数据点，因此向上搜索页0确认，没有更近的点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 关系代数表达式优化（6分）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过pgAdmin 4在PostgreSQL数据库中创建hw4数据库，增加postgis扩展，并连接该数据库"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext sql\n",
    "import time\n",
    "import random\n",
    "\n",
    "# To help render markdown\n",
    "from IPython.core.display import display, HTML\n",
    "from markdown import markdown\n",
    "def render_markdown_raw(m): return display(HTML(markdown(m))) # must be last element of cell.\n",
    "def render_markdown(m): return render_markdown_raw(m.toMD())\n",
    "def cost_markdown(q): \n",
    "    q.reset_count()\n",
    "    get_result(q) # run the counters\n",
    "    return display(HTML(markdown(\"Total Reads: {0}\\n\\n\".format(q.total_count()) + q.toCount(0))))\n",
    "\n",
    "# import the relational algbera operators\n",
    "from relation_algebra import Select, Project, Union, NJoin, CrossProduct, BaseRelation\n",
    "from relation_algebra import get_result, compare_results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql postgresql://postgres:postgres@localhost:5432/hw4\n",
    "\n",
    "SET statement_timeout = 0;\n",
    "SET lock_timeout = 0;\n",
    "SET client_encoding = 'utf-8';\n",
    "SET standard_conforming_strings = on;\n",
    "SET check_function_bodies = false;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关系代数表达式优化参考练习7。创建表R, S, T，并插入数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql\n",
    "drop table if exists R; create table R(a int, b int);\n",
    "drop table if exists S; create table S(b int, c int);\n",
    "drop table if exists T; create table T(c int, d int);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "0 rows affected.\n",
      "100 rows affected.\n",
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "0 rows affected.\n",
      "100 rows affected.\n",
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "0 rows affected.\n",
      "100 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1 = \"\";\n",
    "v2 = \"\";\n",
    "for b in range(0,10,1):\n",
    "    for a in range(0,20,2):\n",
    "        t1 = \" (%d, %d),\" % (a, b)\n",
    "        t2 = \" (%d, %d),\" % (b, a)\n",
    "        v1 = v1 + t1\n",
    "        v2 = v2 + t2\n",
    "r = \"insert into R values\" + v1[:-1] + \";\"\n",
    "s = \"insert into S values\" + v2[:-1] + \";\"\n",
    "t = \"insert into T values\" + v2[:-1] + \";\"\n",
    "%sql delete from R; $r\n",
    "%sql delete from S; $s\n",
    "%sql delete from T; $t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回顾关系代数表达式基本形式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "100 rows affected.\n",
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "100 rows affected.\n",
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "100 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>$\\Pi_{b}$(( R(a,b) ) $\\Join_{b}$ ( S(b,c) ))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0,), (1,), (2,), (8,), (3,), (9,), (4,), (5,), (6,), (7,)]\n"
     ]
    }
   ],
   "source": [
    "r = %sql SELECT * FROM R;\n",
    "R = BaseRelation(r, name=\"R\")\n",
    "s = %sql SELECT * FROM S;\n",
    "S = BaseRelation(s, name=\"S\")\n",
    "t = %sql SELECT * FROM T;\n",
    "T = BaseRelation(t, name=\"T\")\n",
    "\n",
    "x = Project([\"b\"], NJoin(R,S))\n",
    "render_markdown(x)\n",
    "print(get_result(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "熟悉cost_markdown函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 11100</p>\n",
       "<ul>\n",
       "<li>$\\Pi_{['b']}$ [tuples read in: 1000 out: 10]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 10100 out: 1000]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cost_markdown(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在关系数据库系统中，cost主要是I/O cost，即数据页或数据块读取次数（**注意和空间数据库系统的差异**）。在计算cost时，做了以下假设：1. 存储系统没有cache，无论是buffer management还是磁盘上的cache；2. 自然连接实现方式，是基于什么算法？通过构造等价的关系代数表达式，优化以下查询。\n",
    "#### 4.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\sigma_{a=2}$($\\Pi_{a,c}$(( R(a,b) ) $\\Join_{b}$ ( S(b,c) )))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 6), (2, 18), (2, 12), (2, 2), (2, 8), (2, 14), (2, 4), (2, 16), (2, 10), (2, 0)]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 11200</p>\n",
       "<ul>\n",
       "<li>$\\sigma_{a=2}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>$\\Pi_{['a', 'c']}$ [tuples read in: 1000 out: 100]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 10100 out: 1000]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = Select(\"a\", 2, Project([\"a\",\"c\"], NJoin(R,S)))\n",
    "render_markdown(x)\n",
    "print(get_result(x))\n",
    "cost_markdown(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\Pi_{a,c}$(( $\\sigma_{a=2}$(R(a,b)) ) $\\Join_{b}$ ( S(b,c) ))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 16), (2, 6), (2, 18), (2, 8), (2, 10), (2, 0), (2, 12), (2, 2), (2, 14), (2, 4)]\n",
      "True\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 1210</p>\n",
       "<ul>\n",
       "<li>$\\Pi_{['a', 'c']}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 1010 out: 100]<ul>\n",
       "<li>$\\sigma_{a=2}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "y = Project([\"a\",\"c\"], NJoin(Select(\"a\", 2, R), S))\n",
    "render_markdown(y)\n",
    "print(get_result(y))\n",
    "print(compare_results(x,y))\n",
    "cost_markdown(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2（2分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\sigma_{c=0}$($\\Pi_{a,c}$($\\sigma_{b=0}$(( ( R(a,b) ) $\\Join_{b}$ ( S(b,c) ) ) $\\Join_{c}$ ( T(c,d) ))))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(18, 0), (8, 0), (14, 0), (4, 0), (10, 0), (0, 0), (6, 0), (16, 0), (12, 0), (2, 0)]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 116650</p>\n",
       "<ul>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 50 out: 10]<ul>\n",
       "<li>$\\Pi_{['a', 'c']}$ [tuples read in: 500 out: 50]<ul>\n",
       "<li>$\\sigma_{b=0}$ [tuples read in: 5000 out: 500]<ul>\n",
       "<li>$\\Join_{c}$ [tuples read in: 101000 out: 5000]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 10100 out: 1000]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>T(c,d) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = Select(\"c\", 0, Project([\"a\",\"c\"], Select(\"b\", 0, NJoin(NJoin(R, S), T))))\n",
    "render_markdown(x)\n",
    "print(get_result(x))\n",
    "cost_markdown(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\Pi_{a,c}$(( ( $\\sigma_{c=0}$($\\sigma_{b=0}$(S(b,c))) ) $\\Join_{c}$ ( $\\sigma_{c=0}$(T(c,d)) ) ) $\\Join_{b}$ ( $\\sigma_{b=0}$(R(a,b)) ))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(18, 0), (0, 0), (12, 0), (8, 0), (6, 0), (2, 0), (16, 0), (14, 0), (10, 0), (4, 0)]\n",
      "True\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 1431</p>\n",
       "<ul>\n",
       "<li>$\\Pi_{['a', 'c']}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 110 out: 100]<ul>\n",
       "<li>$\\Join_{c}$ [tuples read in: 11 out: 10]<ul>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 10 out: 1]<ul>\n",
       "<li>$\\sigma_{b=0}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>T(c,d) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>$\\sigma_{b=0}$ [tuples read in: 1000 out: 100]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "y =  Project([\"a\",\"c\"], NJoin(NJoin(Select(\"c\", 0, Select(\"b\", 0, S)),Select(\"c\", 0, T) ), Select(\"b\", 0, R)))\n",
    "render_markdown(y)\n",
    "print(get_result(y))\n",
    "print(compare_results(x,y))\n",
    "cost_markdown(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.3（4分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\sigma_{c=0}$($\\Pi_{c}$($\\sigma_{d=2}$($\\sigma_{a=4}$(( R(a,b) ) $\\Join_{b}$ ( ( S(b,c) ) $\\Join_{c}$ ( T(c,d) ) )))))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0,)]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 1065655</p>\n",
       "<ul>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 5 out: 1]<ul>\n",
       "<li>$\\Pi_{['c']}$ [tuples read in: 50 out: 5]<ul>\n",
       "<li>$\\sigma_{d=2}$ [tuples read in: 500 out: 50]<ul>\n",
       "<li>$\\sigma_{a=4}$ [tuples read in: 5000 out: 500]<ul>\n",
       "<li>$\\Join_{b}$ [tuples read in: 50100 out: 5000]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "<li>$\\Join_{c}$ [tuples read in: 1010000 out: 50000]<ul>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "<li>T(c,d) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = Select(\"c\", 0, Project([\"c\"], Select(\"d\", 2, Select(\"a\", 4, NJoin(R, NJoin(S,T))))))\n",
    "render_markdown(x)\n",
    "print(get_result(x))\n",
    "cost_markdown(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\Pi_{c}$(( $\\sigma_{c=0}$($\\sigma_{d=2}$(T(c,d))) ) $\\Join_{c}$ ( ( $\\sigma_{c=0}$(S(b,c)) ) $\\Join_{b}$ ( $\\sigma_{a=4}$(R(a,b)) ) ))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0,)]\n",
      "True\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<p>Total Reads: 1341</p>\n",
       "<ul>\n",
       "<li>$\\Pi_{['c']}$ [tuples read in: 10 out: 1]<ul>\n",
       "<li>$\\Join_{c}$ [tuples read in: 11 out: 10]<ul>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 10 out: 1]<ul>\n",
       "<li>$\\sigma_{d=2}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>T(c,d) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>$\\Join_{b}$ [tuples read in: 110 out: 10]<ul>\n",
       "<li>$\\sigma_{c=0}$ [tuples read in: 100 out: 10]<ul>\n",
       "<li>S(b,c) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "<li>$\\sigma_{a=4}$ [tuples read in: 1000 out: 100]<ul>\n",
       "<li>R(a,b) has 100 tuples </li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>\n",
       "</li>\n",
       "</ul>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "y =  Project([\"c\"],NJoin(Select(\"c\", 0,Select(\"d\", 2, T)), NJoin(Select(\"c\", 0, S), Select(\"a\", 4, R ))))\n",
    "render_markdown(y)\n",
    "print(get_result(y))\n",
    "print(compare_results(x,y))\n",
    "cost_markdown(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "16 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Nested Loop  (cost=2.38..7.47 rows=10 width=4) (actual time=0.036..0.046 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Seq Scan on t  (cost=0.00..2.50 rows=1 width=4) (actual time=0.012..0.016 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: ((c = 0) AND (d = 2))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 99</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Hash Join  (cost=2.38..4.88 rows=10 width=4) (actual time=0.024..0.029 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Hash Cond: (r.b = s.b)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on r  (cost=0.00..2.25 rows=10 width=4) (actual time=0.006..0.010 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (a = 4)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Hash  (cost=2.25..2.25 rows=10 width=8) (actual time=0.013..0.013 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Buckets: 1024  Batches: 1  Memory Usage: 9kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on s  (cost=0.00..2.25 rows=10 width=8) (actual time=0.005..0.010 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (c = 0)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 0.100 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 0.064 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Nested Loop  (cost=2.38..7.47 rows=10 width=4) (actual time=0.036..0.046 rows=10 loops=1)',),\n",
       " ('  ->  Seq Scan on t  (cost=0.00..2.50 rows=1 width=4) (actual time=0.012..0.016 rows=1 loops=1)',),\n",
       " ('        Filter: ((c = 0) AND (d = 2))',),\n",
       " ('        Rows Removed by Filter: 99',),\n",
       " ('  ->  Hash Join  (cost=2.38..4.88 rows=10 width=4) (actual time=0.024..0.029 rows=10 loops=1)',),\n",
       " ('        Hash Cond: (r.b = s.b)',),\n",
       " ('        ->  Seq Scan on r  (cost=0.00..2.25 rows=10 width=4) (actual time=0.006..0.010 rows=10 loops=1)',),\n",
       " ('              Filter: (a = 4)',),\n",
       " ('              Rows Removed by Filter: 90',),\n",
       " ('        ->  Hash  (cost=2.25..2.25 rows=10 width=8) (actual time=0.013..0.013 rows=10 loops=1)',),\n",
       " ('              Buckets: 1024  Batches: 1  Memory Usage: 9kB',),\n",
       " ('              ->  Seq Scan on s  (cost=0.00..2.25 rows=10 width=8) (actual time=0.005..0.010 rows=10 loops=1)',),\n",
       " ('                    Filter: (c = 0)',),\n",
       " ('                    Rows Removed by Filter: 90',),\n",
       " ('Planning Time: 0.100 ms',),\n",
       " ('Execution Time: 0.064 ms',)]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze\n",
    "select p.c from\n",
    "(select S.c from R, S, T where S.c = T.c and S.b = R.b and R.a = 4 and T.d = 2) \n",
    "p where p.c = 0;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "drop index if exists ri;\n",
    "create index ri on R(a asc); "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "16 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Nested Loop  (cost=2.38..7.47 rows=10 width=4) (actual time=0.032..0.042 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Seq Scan on t  (cost=0.00..2.50 rows=1 width=4) (actual time=0.009..0.013 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: ((c = 0) AND (d = 2))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 99</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Hash Join  (cost=2.38..4.88 rows=10 width=4) (actual time=0.022..0.028 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Hash Cond: (r.b = s.b)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on r  (cost=0.00..2.25 rows=10 width=4) (actual time=0.006..0.010 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (a = 4)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Hash  (cost=2.25..2.25 rows=10 width=8) (actual time=0.013..0.013 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Buckets: 1024  Batches: 1  Memory Usage: 9kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on s  (cost=0.00..2.25 rows=10 width=8) (actual time=0.005..0.010 rows=10 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (c = 0)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 1.498 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 0.058 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Nested Loop  (cost=2.38..7.47 rows=10 width=4) (actual time=0.032..0.042 rows=10 loops=1)',),\n",
       " ('  ->  Seq Scan on t  (cost=0.00..2.50 rows=1 width=4) (actual time=0.009..0.013 rows=1 loops=1)',),\n",
       " ('        Filter: ((c = 0) AND (d = 2))',),\n",
       " ('        Rows Removed by Filter: 99',),\n",
       " ('  ->  Hash Join  (cost=2.38..4.88 rows=10 width=4) (actual time=0.022..0.028 rows=10 loops=1)',),\n",
       " ('        Hash Cond: (r.b = s.b)',),\n",
       " ('        ->  Seq Scan on r  (cost=0.00..2.25 rows=10 width=4) (actual time=0.006..0.010 rows=10 loops=1)',),\n",
       " ('              Filter: (a = 4)',),\n",
       " ('              Rows Removed by Filter: 90',),\n",
       " ('        ->  Hash  (cost=2.25..2.25 rows=10 width=8) (actual time=0.013..0.013 rows=10 loops=1)',),\n",
       " ('              Buckets: 1024  Batches: 1  Memory Usage: 9kB',),\n",
       " ('              ->  Seq Scan on s  (cost=0.00..2.25 rows=10 width=8) (actual time=0.005..0.010 rows=10 loops=1)',),\n",
       " ('                    Filter: (c = 0)',),\n",
       " ('                    Rows Removed by Filter: 90',),\n",
       " ('Planning Time: 1.498 ms',),\n",
       " ('Execution Time: 0.058 ms',)]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze\n",
    "select p.c from\n",
    "(select S.c from R, S, T where S.c = T.c and S.b = R.b and R.a = 4 and T.d = 2) \n",
    "p where p.c = 0;"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "PostgreSQL进行了哪些关系代数优化:\n",
    "原先是先进行三个关系的连接再做一系列选择，优化后为：\n",
    "先对R进行 a = 4 的选择，\n",
    "先对S进行 c = 0 的选择,\n",
    "再进行二者的连接；而后对T进行 c = 0 和 d = 2 的选择，最后进行三个关系的连接和投影；\n",
    "\n",
    "PostgreSQL是否使用了创建的索引，并分析原因:\n",
    "没有使用索引;\n",
    "可能原因是数据量较少，顺序扫描的代价比使用索引的代价更小：顺序扫描全表访问的数据块数目少于需要访问索引块再访问数据块的数目；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p>$\\Pi_{c}$(( $\\sigma_{c=0}$($\\sigma_{d=2}$(T(c,d))) ) $\\Join_{c}$ ( ( $\\sigma_{c=0}$(S(b,c)) ) $\\Join_{b}$ ( $\\sigma_{a=4}$(R(a,b)) ) ))</p>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 优化过后的关系代数表达式如下：\n",
    "y =  Project([\"c\"],NJoin(Select(\"c\", 0,Select(\"d\", 2, T)), NJoin(Select(\"c\", 0, S), Select(\"a\", 4, R ))))\n",
    "render_markdown(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 空间索引（18分）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "非空间索引相关练习参考课堂练习6。\n",
    "\n",
    "Natural Earth网站下载[Urban Areas](http://www.naturalearthdata.com/downloads/10m-cultural-vectors/) (12.49 MB version 4.0.0)，[Rivers+lake centerlines](http://www.naturalearthdata.com/downloads/10m-physical-vectors/) (1.73 MB version 4.1.0)，和[Populated Places](http://www.naturalearthdata.com/downloads/10m-cultural-vectors/) (2.68 MB version 4.1.0)数据。\n",
    "\n",
    "在PostgreSQL中导入上述三个shapefile文件，注意导入时**缺省选项是为空间数据创建空间索引**，需要取消这些创建索引选项，手动为Urban_Areas、Rivers和Cities创建空间索引，需要手动修改导入后的关系名。\n",
    "\n",
    "<img src = \"shapefile.png\"/>\n",
    "\n",
    "构造以下空间查询，不能使用with语句。首先在无空间索引下查询，然后创建空间索引，再在有空间索引下查询。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.1 查询每条河流穿越城市区域的次数，查询结果模式为(rivers.name, num)，按次数降序排列（3分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "23 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Sort  (cost=212488009.42..212488011.86 rows=974 width=16) (actual time=38062.753..38062.784 rows=490 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Sort Key: (count(*)) DESC</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Sort Method: quicksort  Memory: 52kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Finalize GroupAggregate  (cost=212487129.56..212487961.07 rows=974 width=16) (actual time=38061.587..38062.636 rows=490 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Group Key: r.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Gather Merge  (cost=212487129.56..212487946.46 rows=974 width=16) (actual time=38061.576..38067.433 rows=743 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Workers Planned: 1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Workers Launched: 1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Partial GroupAggregate  (cost=212486129.55..212486836.88 rows=974 width=16) (actual time=38028.951..38029.279 rows=372 loops=2)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Group Key: r.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Sort  (cost=212486129.55..212486362.08 rows=93012 width=8) (actual time=38028.939..38029.004 rows=934 loops=2)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Key: r.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Method: quicksort  Memory: 67kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Worker 0:  Sort Method: quicksort  Memory: 70kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Nested Loop  (cost=0.00..212478453.67 rows=93012 width=8) (actual time=77.713..38025.971 rows=934 loops=2)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Join Filter: st_crosses(r.geom, u.geom)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Join Filter: 7137745</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Parallel Seq Scan on ne_10m_urban_areas u  (cost=0.00..2333.87 rows=6987 width=1601) (actual time=0.007..6.605 rows=5939 loops=2)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..348.19 rows=1202 width=2874) (actual time=0.001..0.297 rows=1202 loops=11878)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: ((featurecla)::text = &#x27;River&#x27;::text)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 253</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 0.240 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 38067.964 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Sort  (cost=212488009.42..212488011.86 rows=974 width=16) (actual time=38062.753..38062.784 rows=490 loops=1)',),\n",
       " ('  Sort Key: (count(*)) DESC',),\n",
       " ('  Sort Method: quicksort  Memory: 52kB',),\n",
       " ('  ->  Finalize GroupAggregate  (cost=212487129.56..212487961.07 rows=974 width=16) (actual time=38061.587..38062.636 rows=490 loops=1)',),\n",
       " ('        Group Key: r.name',),\n",
       " ('        ->  Gather Merge  (cost=212487129.56..212487946.46 rows=974 width=16) (actual time=38061.576..38067.433 rows=743 loops=1)',),\n",
       " ('              Workers Planned: 1',),\n",
       " ('              Workers Launched: 1',),\n",
       " ('              ->  Partial GroupAggregate  (cost=212486129.55..212486836.88 rows=974 width=16) (actual time=38028.951..38029.279 rows=372 loops=2)',),\n",
       " ('                    Group Key: r.name',),\n",
       " ('                    ->  Sort  (cost=212486129.55..212486362.08 rows=93012 width=8) (actual time=38028.939..38029.004 rows=934 loops=2)',),\n",
       " ('                          Sort Key: r.name',),\n",
       " ('                          Sort Method: quicksort  Memory: 67kB',),\n",
       " ('                          Worker 0:  Sort Method: quicksort  Memory: 70kB',),\n",
       " ('                          ->  Nested Loop  (cost=0.00..212478453.67 rows=93012 width=8) (actual time=77.713..38025.971 rows=934 loops=2)',),\n",
       " ('                                Join Filter: st_crosses(r.geom, u.geom)',),\n",
       " ('                                Rows Removed by Join Filter: 7137745',),\n",
       " ('                                ->  Parallel Seq Scan on ne_10m_urban_areas u  (cost=0.00..2333.87 rows=6987 width=1601) (actual time=0.007..6.605 rows=5939 loops=2)',),\n",
       " ('                                ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..348.19 rows=1202 width=2874) (actual time=0.001..0.297 rows=1202 loops=11878)',),\n",
       " (\"                                      Filter: ((featurecla)::text = 'River'::text)\",),\n",
       " ('                                      Rows Removed by Filter: 253',),\n",
       " ('Planning Time: 0.240 ms',),\n",
       " ('Execution Time: 38067.964 ms',)]"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql\n",
    "explain analyze\n",
    "select r.name,count(*) num from ne_10m_rivers_lake_centerlines r, ne_10m_urban_areas u \n",
    "where r.featurecla = 'River' and ST_Crosses(r.geom,u.geom) group by r.name order by num desc;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划回答以下问题"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "城市区域和河流的连接操作使用了哪个Join算法：Nested Loop\n",
    "基于河流分组使用了什么算法实现：\n",
    "先进行quicksort，再进行Partial GroupAggregate，再把各个部分的结果Gather Merge在一起，最后Finalize GroupAggregate\n",
    "按次数降序排列使用了什么算法实现：quicksort \n",
    "按次数降序排列是在磁盘还是内存完成：在内存完成"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.2 查询在亚马逊河流10个单位距离内的所有城市，查询结果模式为(cities.gid, cities.name) (使用ST_Distance实现)（3分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "13 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Unique  (cost=184968.83..184987.19 rows=2448 width=13) (actual time=149.310..149.349 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Sort  (cost=184968.83..184974.95 rows=2448 width=13) (actual time=149.308..149.318 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Key: p.gid, p.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Method: quicksort  Memory: 39kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Nested Loop  (cost=0.00..184831.04 rows=2448 width=13) (actual time=6.233..149.189 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Join Filter: (st_distance(r.geom, p.geom) &lt; &#x27;10&#x27;::double precision)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Join Filter: 7070</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.543..1.347 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (((name_zh)::text ~~ &#x27;%亚马逊%&#x27;::text) AND ((featurecla)::text = &#x27;River&#x27;::text))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 1454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_populated_places p  (cost=0.00..812.43 rows=7343 width=45) (actual time=0.009..3.062 rows=7343 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 1.893 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 153.055 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Unique  (cost=184968.83..184987.19 rows=2448 width=13) (actual time=149.310..149.349 rows=273 loops=1)',),\n",
       " ('  ->  Sort  (cost=184968.83..184974.95 rows=2448 width=13) (actual time=149.308..149.318 rows=273 loops=1)',),\n",
       " ('        Sort Key: p.gid, p.name',),\n",
       " ('        Sort Method: quicksort  Memory: 39kB',),\n",
       " ('        ->  Nested Loop  (cost=0.00..184831.04 rows=2448 width=13) (actual time=6.233..149.189 rows=273 loops=1)',),\n",
       " (\"              Join Filter: (st_distance(r.geom, p.geom) < '10'::double precision)\",),\n",
       " ('              Rows Removed by Join Filter: 7070',),\n",
       " ('              ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.543..1.347 rows=1 loops=1)',),\n",
       " (\"                    Filter: (((name_zh)::text ~~ '%亚马逊%'::text) AND ((featurecla)::text = 'River'::text))\",),\n",
       " ('                    Rows Removed by Filter: 1454',),\n",
       " ('              ->  Seq Scan on ne_10m_populated_places p  (cost=0.00..812.43 rows=7343 width=45) (actual time=0.009..3.062 rows=7343 loops=1)',),\n",
       " ('Planning Time: 1.893 ms',),\n",
       " ('Execution Time: 153.055 ms',)]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze\n",
    "select distinct p.gid, p.name from ne_10m_rivers_lake_centerlines r, ne_10m_populated_places p \n",
    "where r.featurecla = 'River' and r.name_zh like '%亚马逊%' and ST_Distance(r.geom,p.geom) < 10;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划回答以下问题"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "查询规划估计的查询结果行数为：2448\n",
    "查询语句实际的查询结果行数为：273\n",
    "结果去重时(distinct)采用了什么算法实现：quicksort 排序算法排序后去重\n",
    "ST_Distance(geometry, geometry)的cost值为(pgAdmin中查找)：10000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.3 为上述三个关系创建GiST空间索引（3分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql\n",
    "drop index if exists rivers_geom_idx;\n",
    "drop index if exists cities_geom_idx;\n",
    "drop index if exists urban_areas_geom_idx;\n",
    "create index rivers_geom_idx on ne_10m_rivers_lake_centerlines using GIST(geom);\n",
    "create index urban_areas_geom_idx on ne_10m_urban_areas using GIST(geom);\n",
    "create index cities_geom_idx on ne_10m_populated_places using GIST(geom);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过pg_class关系查询索引存储所需的数据页数和行数，即Block数目和城市区域、河流与城市数目"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "1 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>relpages</th>\n",
       "        <th>reltuples</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>86</td>\n",
       "        <td>11878.0</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[(86, 11878.0)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql select relpages, reltuples from pg_class where relname = 'urban_areas_geom_idx'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "1 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>relpages</th>\n",
       "        <th>reltuples</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>9</td>\n",
       "        <td>1455.0</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[(9, 1455.0)]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql select relpages, reltuples from pg_class where relname = 'rivers_geom_idx'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "1 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>relpages</th>\n",
       "        <th>reltuples</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>47</td>\n",
       "        <td>7343.0</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[(47, 7343.0)]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql select relpages, reltuples from pg_class where relname = 'cities_geom_idx'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.4 再次执行5.1的查询语句（3分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "15 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Sort  (cost=35604.24..35606.67 rows=974 width=16) (actual time=2376.822..2376.835 rows=490 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Sort Key: (count(*)) DESC</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Sort Method: quicksort  Memory: 52kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  HashAggregate  (cost=35546.15..35555.89 rows=974 width=16) (actual time=2376.695..2376.752 rows=490 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Group Key: r.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Nested Loop  (cost=0.15..34755.54 rows=158121 width=8) (actual time=0.502..2374.822 rows=1867 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..348.19 rows=1202 width=2874) (actual time=0.008..0.915 rows=1202 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: ((featurecla)::text = &#x27;River&#x27;::text)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 253</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Index Scan using urban_areas_geom_idx on ne_10m_urban_areas u  (cost=0.15..28.62 rows=1 width=1601) (actual time=0.365..1.969 rows=2 loops=1202)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Index Cond: (geom &amp;&amp; r.geom)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: st_crosses(r.geom, geom)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 2.495 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 2377.011 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Sort  (cost=35604.24..35606.67 rows=974 width=16) (actual time=2376.822..2376.835 rows=490 loops=1)',),\n",
       " ('  Sort Key: (count(*)) DESC',),\n",
       " ('  Sort Method: quicksort  Memory: 52kB',),\n",
       " ('  ->  HashAggregate  (cost=35546.15..35555.89 rows=974 width=16) (actual time=2376.695..2376.752 rows=490 loops=1)',),\n",
       " ('        Group Key: r.name',),\n",
       " ('        ->  Nested Loop  (cost=0.15..34755.54 rows=158121 width=8) (actual time=0.502..2374.822 rows=1867 loops=1)',),\n",
       " ('              ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..348.19 rows=1202 width=2874) (actual time=0.008..0.915 rows=1202 loops=1)',),\n",
       " (\"                    Filter: ((featurecla)::text = 'River'::text)\",),\n",
       " ('                    Rows Removed by Filter: 253',),\n",
       " ('              ->  Index Scan using urban_areas_geom_idx on ne_10m_urban_areas u  (cost=0.15..28.62 rows=1 width=1601) (actual time=0.365..1.969 rows=2 loops=1202)',),\n",
       " ('                    Index Cond: (geom && r.geom)',),\n",
       " ('                    Filter: st_crosses(r.geom, geom)',),\n",
       " ('                    Rows Removed by Filter: 8',),\n",
       " ('Planning Time: 2.495 ms',),\n",
       " ('Execution Time: 2377.011 ms',)]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql\n",
    "explain analyze\n",
    "select r.name,count(*) num from ne_10m_rivers_lake_centerlines r, ne_10m_urban_areas u \n",
    "where r.featurecla = 'River' and ST_Crosses(r.geom,u.geom) group by r.name order by num desc;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划回答以下问题"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "查询规划利用了哪些空间索引： urban_areas_geom_idx \n",
    "城市区域和河流通过精确几何判断为穿越的行数与空间索引通过包围盒判断可能穿越的行数比值：2 / 10 = 0.2000\n",
    "与5.1相比，查询规划估计的cost值(最大值)减少了(任意单位)：212488011.86 - 35606.67 = 212452405.19\n",
    "与5.1相比，查询语句实际运行时间减少了(ms)：38067.964 - 2376.835 = 35691.129"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.5 再次查询5.2，使用ST_DWithin实现（4分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "14 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Unique  (cost=387.36..387.87 rows=69 width=13) (actual time=6.064..6.102 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Sort  (cost=387.36..387.53 rows=69 width=13) (actual time=6.063..6.071 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Key: p.gid, p.name</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort Method: quicksort  Memory: 39kB</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Nested Loop  (cost=0.40..385.25 rows=69 width=13) (actual time=0.285..6.003 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.200..0.503 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (((name_zh)::text ~~ &#x27;%亚马逊%&#x27;::text) AND ((featurecla)::text = &#x27;River&#x27;::text))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 1454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Index Scan using cities_geom_idx on ne_10m_populated_places p  (cost=0.40..33.41 rows=1 width=45) (actual time=0.057..5.450 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Index Cond: (geom &amp;&amp; st_expand(r.geom, &#x27;10&#x27;::double precision))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: st_dwithin(r.geom, geom, &#x27;10&#x27;::double precision)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 43</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 1.109 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 6.295 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Unique  (cost=387.36..387.87 rows=69 width=13) (actual time=6.064..6.102 rows=273 loops=1)',),\n",
       " ('  ->  Sort  (cost=387.36..387.53 rows=69 width=13) (actual time=6.063..6.071 rows=273 loops=1)',),\n",
       " ('        Sort Key: p.gid, p.name',),\n",
       " ('        Sort Method: quicksort  Memory: 39kB',),\n",
       " ('        ->  Nested Loop  (cost=0.40..385.25 rows=69 width=13) (actual time=0.285..6.003 rows=273 loops=1)',),\n",
       " ('              ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.200..0.503 rows=1 loops=1)',),\n",
       " (\"                    Filter: (((name_zh)::text ~~ '%亚马逊%'::text) AND ((featurecla)::text = 'River'::text))\",),\n",
       " ('                    Rows Removed by Filter: 1454',),\n",
       " ('              ->  Index Scan using cities_geom_idx on ne_10m_populated_places p  (cost=0.40..33.41 rows=1 width=45) (actual time=0.057..5.450 rows=273 loops=1)',),\n",
       " (\"                    Index Cond: (geom && st_expand(r.geom, '10'::double precision))\",),\n",
       " (\"                    Filter: st_dwithin(r.geom, geom, '10'::double precision)\",),\n",
       " ('                    Rows Removed by Filter: 43',),\n",
       " ('Planning Time: 1.109 ms',),\n",
       " ('Execution Time: 6.295 ms',)]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze \n",
    "select distinct p.gid, p.name from ne_10m_rivers_lake_centerlines r, ne_10m_populated_places p \n",
    "where r.featurecla = 'River' and r.name_zh like '%亚马逊%' and ST_DWithin(r.geom,p.geom,10);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划回答以下问题"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "查询规划利用了哪些空间索引：cities_geom_idx \n",
    "ST_DWithin(geometry, geomtry)的cost值为(在pgAdmin中查找)：10000\n",
    "河流和城市通过精确几何判断距离小于10的行数与空间索引通过包围盒判断距离可能小于10的行数比值：\n",
    "43 / （273+43） = 0.1361\n",
    "与5.2相比，查询规划估计的cost值(最大值)减少了(任意单位)：184987.19 - 387.87 = 184599.32\n",
    "与5.2相比，查询语句实际运行时间减少了(ms)：149.349 - 6.102  = 143.247"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5.6 设置查询选项，如enable_indexscan，再次执行5.5查询语句（2分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql SET enable_indexscan = false;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "12 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Nested Loop  (cost=4.41..385.25 rows=69 width=13) (actual time=0.321..6.063 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.199..0.499 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (((name_zh)::text ~~ &#x27;%亚马逊%&#x27;::text) AND ((featurecla)::text = &#x27;River&#x27;::text))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 1454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Bitmap Heap Scan on ne_10m_populated_places p  (cost=4.41..33.42 rows=1 width=45) (actual time=0.116..5.534 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: st_dwithin(r.geom, geom, &#x27;10&#x27;::double precision)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 43</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Heap Blocks: exact=97</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&gt;  Bitmap Index Scan on cities_geom_idx  (cost=0.00..4.41 rows=1 width=0) (actual time=0.059..0.059 rows=316 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Index Cond: (geom &amp;&amp; st_expand(r.geom, &#x27;10&#x27;::double precision))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 0.236 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 6.106 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Nested Loop  (cost=4.41..385.25 rows=69 width=13) (actual time=0.321..6.063 rows=273 loops=1)',),\n",
       " ('  ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.199..0.499 rows=1 loops=1)',),\n",
       " (\"        Filter: (((name_zh)::text ~~ '%亚马逊%'::text) AND ((featurecla)::text = 'River'::text))\",),\n",
       " ('        Rows Removed by Filter: 1454',),\n",
       " ('  ->  Bitmap Heap Scan on ne_10m_populated_places p  (cost=4.41..33.42 rows=1 width=45) (actual time=0.116..5.534 rows=273 loops=1)',),\n",
       " (\"        Filter: st_dwithin(r.geom, geom, '10'::double precision)\",),\n",
       " ('        Rows Removed by Filter: 43',),\n",
       " ('        Heap Blocks: exact=97',),\n",
       " ('        ->  Bitmap Index Scan on cities_geom_idx  (cost=0.00..4.41 rows=1 width=0) (actual time=0.059..0.059 rows=316 loops=1)',),\n",
       " (\"              Index Cond: (geom && st_expand(r.geom, '10'::double precision))\",),\n",
       " ('Planning Time: 0.236 ms',),\n",
       " ('Execution Time: 6.106 ms',)]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze\n",
    "select p.gid, p.name from ne_10m_rivers_lake_centerlines r, ne_10m_populated_places p \n",
    "where r.featurecla = 'River' and r.name_zh like '%亚马逊%' and ST_DWithin(r.geom,p.geom,10);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划，回答该查询是否利用了索引，哪些索引，如何用来加速判断？"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "利用了cities_geom_idx索引；\n",
    "在cities_geom_idx上面进行了Bitmap Index Scan，对ST_DWithin(r.geom,p.geom,10)函数进行加速判断；\n",
    "加速判断的方法是判断r.geom扩充10后的包围盒是否和p.geom的包围盒有交叠；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql SET enable_bitmapscan = false;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "9 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>QUERY PLAN</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Nested Loop  (cost=0.00..184812.69 rows=69 width=13) (actual time=6.005..141.528 rows=273 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Join Filter: st_dwithin(r.geom, p.geom, &#x27;10&#x27;::double precision)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;Rows Removed by Join Filter: 7070</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.240..0.593 rows=1 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Filter: (((name_zh)::text ~~ &#x27;%亚马逊%&#x27;::text) AND ((featurecla)::text = &#x27;River&#x27;::text))</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rows Removed by Filter: 1454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>&nbsp;&nbsp;-&gt;  Seq Scan on ne_10m_populated_places p  (cost=0.00..812.43 rows=7343 width=45) (actual time=0.007..1.189 rows=7343 loops=1)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Planning Time: 0.229 ms</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>Execution Time: 141.562 ms</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('Nested Loop  (cost=0.00..184812.69 rows=69 width=13) (actual time=6.005..141.528 rows=273 loops=1)',),\n",
       " (\"  Join Filter: st_dwithin(r.geom, p.geom, '10'::double precision)\",),\n",
       " ('  Rows Removed by Join Filter: 7070',),\n",
       " ('  ->  Seq Scan on ne_10m_rivers_lake_centerlines r  (cost=0.00..351.82 rows=1 width=2866) (actual time=0.240..0.593 rows=1 loops=1)',),\n",
       " (\"        Filter: (((name_zh)::text ~~ '%亚马逊%'::text) AND ((featurecla)::text = 'River'::text))\",),\n",
       " ('        Rows Removed by Filter: 1454',),\n",
       " ('  ->  Seq Scan on ne_10m_populated_places p  (cost=0.00..812.43 rows=7343 width=45) (actual time=0.007..1.189 rows=7343 loops=1)',),\n",
       " ('Planning Time: 0.229 ms',),\n",
       " ('Execution Time: 141.562 ms',)]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql \n",
    "explain analyze\n",
    "select p.gid, p.name from ne_10m_rivers_lake_centerlines r, ne_10m_populated_places p \n",
    "where r.featurecla = 'River' and r.name_zh like '%亚马逊%' and ST_DWithin(r.geom,p.geom,10);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于上述查询规划，回答该查询是否利用了索引，哪些索引，如何用来加速判断？"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "没有利用索引；\n",
    "使用顺序扫描来进行选择操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * postgresql://postgres:***@localhost:5432/hw4\n",
      "Done.\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql\n",
    "SET enable_indexscan = true;\n",
    "SET enable_bitmapscan = true;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. 查询规划选择 (附加题3分)\n",
    "\n",
    "关系R(A, B), S(B, C), T(C, D)统计信息如下：<br/>\n",
    "T(R) = $10^5$, T(S) = 6 \\* $10^6$, T(T) = 5 \\* $10^4$<br/>\n",
    "B(R) = 100, B(S) = 3000, B(T) = 40000<br/>\n",
    "V(R, A) = 5 \\* $10^4$, V(R,B) = V(S, B) = 3 \\* $10^3$, V(S, C) = V(T, C) = 2 \\* $10^4$, V(T, D) = $10^4$<br/>\n",
    "创建了非聚集索引R.A, R.B, S.C, T.D和聚集索引S.B, T.C。\n",
    "\n",
    "6.1 查询结果行数估计<br/>\n",
    "&ensp;&ensp;&ensp; Select \\*<br/>\n",
    "&ensp;&ensp;&ensp; From R, S, T<br/>\n",
    "&ensp;&ensp;&ensp; Where R.A = 2432 and R.B = S.B and S.C = T.C and T.D = 1234;"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "T(R)/V(R, A) = 2\n",
    "T(S)/ V(S, B) = 2000\n",
    "T(T)/V(T, C) = 2.5\n",
    "2*2000*2.5/V(T, D) = 1\n",
    "查询结果行数估计为1行"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6.2 物理查询规划1的cost = 2 + 2 \\* 1 + 4000 \\* 2 = 8004 (具体看Lecture 8)\n",
    "<img width = 500 src = 'physicalplan1.png' />\n",
    "6.3 物理查询规划2如下图所示，估计对应的cost\n",
    "<img width = 500 src = 'physicalplan2.png' />"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "cost = 2 + 2 + 4 = 8\n",
    "与物理查询规划1相比，有何差别？\n",
    "使用在内存中的hash join代替了index join，并将最后的选择操作下推至执行join操作之前。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 作业感想\n",
    "\n",
    "收获:-)，疑惑:-|，吐槽:-(，...，你的反馈很重要"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
